package LineCode.剑指Offer.递归和循环;

/**
 * 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
 */
public class 变态跳台阶 {

    public static void main(String[] args) {
        System.out.println(JumpFloorII(3));
    }

    /**
     * 递归
     * @param target
     * @return
     */
    public static int JumpFloorII(int target) {
        if (target == 0) return 1;
        if (target < 0) return 0;
        int num = 1;
        while (--target > 0)
            num += JumpFloorII(target);
        return num;
    }

    /**
     * 找规律
     * @param target
     * @return
     */
    public static int JumpFloorII2(int target) {
        return (int)Math.pow(2,target-1);
    }
}
